<!DOCTYPE html>
<html lang="en">
<head>
    <meta charset="UTF-8">
    <meta name="viewport" content="width=device-width, initial-scale=1.0">
    <title>4.希尔排序</title>
</head>
<body>
    
</body>
<script>
    // let array = [2,31,21,441,2,41,23,1,1,0,2,14,1,21]
    let array = [5,7,8,3,1,2,4,6]

    let shellSort = function(array) {
        let arrayLength = array.length
        let gaps = []
        gap = arrayLength
        while(gap !== 1) {
            gap = Math.floor(gap/2) // gap >> 1
            gaps.unshift(gap)
        }
        console.log('gaps:', gaps)
        while(gap = gaps.pop()) {
            // // 这里是插入排序
            // for(let g=0;g<gap;g++) { 
            //     for(let i = g + gap;i<arrayLength; i=i+gap) {
            //         target = array[i]
            //         if(target < array[i-gap]) {
            //             let j = i
            //             while(j>0 && array[j-gap] > target) {
            //                 array[j] = array[j-gap]
            //                 j=j-gap
            //             }
            //             array[j] = target
            //         }                    
            //     }
            // }
            for(let g=0;g<gap;g++) {
                for(let i=g+gap;i<arrayLength; i++) {
                    target = array[i]
                    let j = i - gap
                    while(j>0 && array[j] > target) {
                        array[j+gap] = array[j]
                        j = j-gap
                    }
                    array[j+gap] = target
                }
            }
        }
    }

    shellSort(array)
    console.log('输出希尔排序后的结果:', array)
</script>
</html>